This invention relates generally to communication systems, and more particularly to an Automatic Repeat Request (ARQ) protocol useful for transferring delay-sensitive data between sending and receiving devices over error-prone communication links.
Historically, communication systems have employed separate protocols for the transfer of delay-insensitive data and delay-sensitive data from a sender to receiver. Delay-insensitive data transfer services have used Automatic Repeat Request (ARQ) protocols that allow for reliable transfer of the data stream regardless of delay. ARQ protocols permit the receiver of a stream of data blocks to request the retransmission of data blocks that were either not received or received corrupted from the sender. ARQ protocols are often accompanied with forward error correction (FEC) to reduce the number of required retransmissions.
Examples of known ARQ protocols include Stop-and-Wait, Go-Back-N, and Selective Repeat. In Stop-and-Wait ARQ, a receiver sends an acknowledge (ACK) message to a transmitter after a given block is received successfully. The transmitter waits until the ACK message is received for a given block before it proceeds with transmitting the next block in a sequence of blocks. If the receiver detects an error in a given block, it sends a negative acknowledgement (NACK) message to the transmitter, and the transmitter then retransmits the given block. In Go-Back-N and Select Repeat ARQ, the transmitter is sending message data and the receiver is sending acknowledgment data simultaneously. After transmitting a given block, the transmitter continues to transmit additional blocks in the sequence even though an ACK has not yet been received for that given block. In Go-Back-N ARQ, if the receiver sends a NACK message indicating that the given block needs to be retransmitted, the transmitter will retransmit the given block and all subsequent blocks that were transmitted prior to receiving the NACK message. In Selective Repeat ARQ, the transmitter retransmits the given block, but then resumes the transmission sequence where it left off prior to receiving the NACK message. A block subsequent to the erroneous block is not retransmitted unless it is specifically identified as erroneous by a NACK message.
The Stop-and-Wait, Go-Back-N, and Selective Repeat ARQ protocols were developed to transfer delay-insensitive blocks from transmitter to receiver. For example, these protocols are well-suited to transferring a data file over an error-prone link, where the file must be transferred perfectly but the time required to perform the file transfer is of secondary importance. However, the known ARQ procedures are not well suited for transferring delay-sensitive data over error-prone communication links. For example, in packetized voice and video applications, transfer time is of primary importance. After a certain elapsed time the packet is of no value to the receiver. In these delay-sensitive applications, the transmitter and receiver should stop attempting to transfer blocks from a packet which is no longer of value to the receiver. Historically, delay-sensitive services did not use an ARQ protocol, but rather used forward error correction (FEC) techniques to accomplish error correction. Recent improvements in bandwidth management algorithms and physical layer data transfer technologies now permit limited retransmission of blocks within delay-sensitive data streams. However, the known art does not feature an ARQ protocol capable of handling the demands of both delay-sensitive and delay-insensitive data streams over a high transfer rate, high transfer delay data link. Furthermore, there does not exist an ARQ protocol sufficiently flexible to dynamically adapt to changes in data stream delay sensitivity.
An ARQ protocol capable of transferring delay-sensitive blocks must include a mechanism by which a transmitter (or receiver) can inform its peer entity that attempts to retransmit a particular block are no longer useful and will be (or should be) terminated. The known art employs two methods by which a transmitter can inform a receiver that it no longer wishes to transfer a particular block or blocks (i.e., prematurely terminate block transfer). In the first method, a field is added to the block transfer request message indicating that a particular block or blocks will not be transferred. For example, the block transfer request message might indicate that the block with sequence number 22 is being transferred and that further transmission attempts for the block with sequence number 19 will be halted. In the second method, a separate message is sent from transmitter or receiver indicating which block or blocks will not be transferred. The European Telecommunications Standards Institute (ETSI) HIPERLAN/2 ARQ protocol employs this method.
These two block transfer termination methods share a serious drawback. If the message specifying which block or blocks will not be transferred is lost, then the transmitter must detect by some mechanism that this has occurred and retransmit the request. These additional termination request messages increase the bandwidth consumption and block transfer delay of the ARQ protocol. Also, the ARQ protocol becomes much more complex.
A popular technique for increasing the efficiency of Selective Repeat ARQ protocols is to utilize a single message to negatively acknowledge multiple blocks. The known art employs a bit field, where each bit in the field provides the reception status of a single block. For example, if a bit within the bit field is 1, the corresponding block has been received successfully (ACK). If a bit within the bit field is 0, the corresponding block has not been received successfully (NACK). However, a problem with the bit field approach is that as data transfer rates and data transfer delays increase, the number of bits within the bit field must become quite large in order to provide useful negative acknowledgement information to the sender. This is because the receiver may have a large number of consecutive blocks to negatively acknowledge, but a limited number of bits with which to do it. This is a particular problem on high data rate wireless links during fading conditions. A large bit field requires a large negative acknowledgement message, which can prevent piggy-backing. In piggybacking, a data transfer request message for a stream flowing in one direction is packaged with a data transfer response message (ACK and/or NACK) for a stream flowing in the other direction. A data link supporting ARQ message piggybacking is usually much more efficient than a corresponding data link without piggybacking.
Moreover, existing ARQ protocols do not have a means by which an external entity (such as a bandwidth manager) can dynamically alter key aspects of ARQ protocol performance in response to changes in link operating conditions. Instead, ARQ protocol performance is rigidly fixed by the particular procedures incorporated into the protocol. However, such flexibility would be useful to engineers designing advanced scheduling algorithms for managing the transfer of multiple, simultaneous, independent delay-sensitive data streams over error-prone links. For example, the ability to dynamically change the bandwidth consumption and aggregate block transfer delay performance of an ARQ protocol would allow a link bandwidth manager to tailor the performance of the ARQ protocol to the current link load. If the link is lightly loaded, ARQ bandwidth consumption could be increased with a corresponding decrease in aggregate block transfer delay. If the link becomes congested, the bandwidth manager could scale back the ARQ bandwidth consumption with a corresponding increase in aggregate block transfer delay.
The foregoing discussion indicates that there is a need for an ARQ protocol that is capable of handling the demands of both delay-sensitive and delay-insensitive data transfers over a high transfer rate, high transfer delay data link subject to burst errors. Furthermore, there is a need for an ARQ protocol with data transfer reliability, delay, and bandwidth consumption performance that can be adapted dynamically by the transmitter or receiver to compensate for changes in link operating conditions. The present invention is directed to satisfying or at least partially satisfying these needs.